Baraj pentru Lotul olimpic, Bucuresti, mai 1997
Problema 3 (Autostrazi si orase) - Vlad Marius
Dificultate: C4

	Intr-o tara exista N orase (N<=100) si M aurostrazi (M<=100). Fiecare
autostrada face legatura intre doua orase. Fiecare autostrada are o taxa pentru
fiecare ora de mers. Aceasta taxa este variabila in timp. La intrarea cu autoturismul
pe o autostrada se plateste taxa pentru toate orele parcurse pana la iesirea de
pe autostrada la valoarea timpului de intrare pe autostrada.
	Intr-un oras de pe traseu se poate parca (optional) autoturismul, dupa
care se pleaca pe o autostrada care face legatura cu alt oras. Fiecare oras are
o taxa fixa pentru fiecare ora de parcare in orasul respectiv. In orasul initial
A si orasul final B parcarea este gratuita.
	Avand la dispozitie un autoturism personal, trebuie sa ajungeti dintr-un
oras A intr-un oras B astfel incat costul total platit sa fie minim. Initial, la
momentul T=0 va aflati in orasul A iar la momentul TF (TF<=100) trebuie sa va
aflati in orasul B.
Fisier de intrare: INPUT.3
N M			- numarul de orase si numarul de strazi
A B TF			- orasul de plecare, de sosire si timpul alocat deplasarii
P1 P1 .. PN		- costul parcarii pe ora in orasul 1,2,..,N
O1 O2 L			- prima autostrada, intre O1 si O2; 
			     distanta dintre ele se parcurge in L ore
C(0) C(1).. C(TF-1)	- costul pentru o ora de mers pe prima autostrada daca 
			   se intra la momentele 0,1,..,TF-1
..........
O1 O2 L			- a M-a autostrada, intre O1 si O2; 
			     distanta dintre ele se parcurge in L ore
C(0) C(1).. C(TF-1)	- costul pentru o ora de mers pe autostrada M daca se
			   intra la momentele 0,1,..,TF-1

Fisier de iesire: OUTPUT.3
C		- costul minim gasit
O		- numarul de orase prin care se trece (inclusiv A si B);
T(1) N(1)	- timp de parcare in orasul A, autostrada care iese din A;
........
T(O-1) N(O-1)	- timp de parcare in orasul O, autostrada care iese din O;
T(O)		- timp de stationare in orasul B;
 Incazul in care nu exista solutie, se va scrie in fisier:
0
0
Exemplu:
Pentru fisierul INPUT.3:
3 2
1 3 5
0 1 0
1 2 2
2 5 5 5 5
2 3 2
5 5 5 1 5
un rezultat corect poate fi:
7
3
0 1
1 2
0

Timp de executie: 10 secunde/test
=================================
Solutie (Vlad Marius)
program Autostrazi_si_Orase;
type autostr=record
       O1,O2,L:byte;
       Cost:array[0..100] of byte;
      end;
     tipdin=record
       Cost:word;
       Autostrada:byte;
       Parcare:byte;
      end;
     tipout=record
       Asteptare:byte;
       Autostrada:byte;
      end;
var i,j,k,l,i1,j1,n,m:integer;
    fi,fo:text;
    Parcare:array[1..100] of integer;
    Autostrada:array[1..100] of autostr;
    A,B,TF:integer;
    Dinamic:array[0..100,1..100] of tipdin;
    Output:array[1..100] of tipout;

begin
 assign(fi,'INPUT.T6');
 assign(fo,'INPUT.R6');
 reset(fi);
 rewrite(fo);
 readln(fi,N,M);
 readln(fi,A,B,TF);
 for i:=1 to N do read(fi,Parcare[i]);
 readln(fi);
 for i:=1 to M do
  begin
   readln(fi,Autostrada[i].O1,Autostrada[i].O2,Autostrada[i].L);
   for j:=0 to TF-1 do read(fi,Autostrada[i].Cost[j]);
   readln(fi);
  end;
 writeln(fo,n,' ',2*m);
 writeln(fo,a,' ',b,' ',tf);
 for i:=1 to n do write(fo,Parcare[i],' ');
 writeln(fo);
 for i:=1 to m do
  begin
   writeln(fo,Autostrada[i].o1,' ',Autostrada[i].o2,' ',Autostrada[i].l);
   for j:=0 to tf-1 do write(fo,Autostrada[i].cost[j],' ');
   writeln(fo);
   writeln(fo,Autostrada[i].o2,' ',Autostrada[i].o1,' ',Autostrada[i].l);
   for j:=0 to tf-1 do write(fo,Autostrada[i].cost[j],' ');
   writeln(fo);
  end;
 close(fi);
 close(fo);
end.
==================================
	TESTE

Intrare:

test 1:
4 10
1 3 7
0 1 0 1 
1 2 5
2 3 4 3 1 3 4 
2 1 5
2 3 4 3 1 3 4 
1 4 5
1 2 3 4 5 6 7 
4 1 5
1 2 3 4 5 6 7 
2 3 5
1 1 1 1 1 1 1 
3 2 5
1 1 1 1 1 1 1 
2 4 1
2 2 2 2 2 2 2 
4 2 1
2 2 2 2 2 2 2 
4 3 3
2 3 4 5 8 7 6 
3 4 3
2 3 4 5 8 7 6 
---------------------------------------
test 2:
4 10
1 3 8
0 1 0 1 
1 2 5
2 3 4 3 1 3 4 4 
2 1 5
2 3 4 3 1 3 4 4 
1 4 5
1 2 3 4 5 6 7 7 
4 1 5
1 2 3 4 5 6 7 7 
2 3 5
1 1 1 1 1 1 1 1 
3 2 5
1 1 1 1 1 1 1 1 
2 4 1
2 2 2 2 2 2 2 2 
4 2 1
2 2 2 2 2 2 2 2 
4 3 3
2 3 4 5 8 7 6 6 
3 4 3
2 3 4 5 8 7 6 6 
-----------------------------------
Test 3:
6 10
1 6 20
0 1 1 1 1 0 
1 2 2
10 0 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 
2 1 2
10 0 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 
2 3 2
10 10 10 10 10 0 10 10 10 10 10 10 10 10 10 10 10 10 10 10 
3 2 2
10 10 10 10 10 0 10 10 10 10 10 10 10 10 10 10 10 10 10 10 
3 4 2
10 10 10 10 10 10 10 10 10 0 10 10 10 10 10 10 10 10 10 10 
4 3 2
10 10 10 10 10 10 10 10 10 0 10 10 10 10 10 10 10 10 10 10 
4 5 2
10 10 10 10 10 10 10 10 10 10 10 10 10 0 10 10 10 10 10 10 
5 4 2
10 10 10 10 10 10 10 10 10 10 10 10 10 0 10 10 10 10 10 10 
5 6 2
10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 0 10 10 
6 5 2
10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 0 10 10 
------------------------------------------------
test 4:
6 12
1 6 10
0 100 100 100 100 0 
1 2 2
1 1 1 1 1 1 1 1 1 1 
2 1 2
1 1 1 1 1 1 1 1 1 1 
2 3 2
90 90 0 90 90 90 90 90 90 90 
3 2 2
90 90 0 90 90 90 90 90 90 90 
3 4 1
1 1 1 1 1 1 1 1 1 1 
4 3 1
1 1 1 1 1 1 1 1 1 1 
4 5 1
1 1 1 1 1 1 1 1 1 1 
5 4 1
1 1 1 1 1 1 1 1 1 1 
5 3 1
1 1 1 1 1 1 1 1 1 1 
3 5 1
1 1 1 1 1 1 1 1 1 1 
3 6 2
60 60 60 60 60 60 60 0 60 60 
6 3 2
60 60 60 60 60 60 60 0 60 60 
-------------------------------------
test 5:
6 12
1 6 10
0 100 100 100 100 0 
1 2 2
1 1 1 1 1 1 1 1 1 1 
2 1 2
1 1 1 1 1 1 1 1 1 1 
2 3 2
90 90 0 90 90 90 90 90 90 90 
3 2 2
90 90 0 90 90 90 90 90 90 90 
3 4 1
1 1 1 1 1 1 1 1 1 1 
4 3 1
1 1 1 1 1 1 1 1 1 1 
4 5 1
1 1 1 1 1 1 1 1 1 1 
5 4 1
1 1 1 1 1 1 1 1 1 1 
5 3 1
1 1 1 1 1 1 1 1 1 1 
3 5 1
1 1 1 1 1 1 1 1 1 1 
3 6 2
60 60 60 60 60 60 60 0 60 60 
6 3 2
60 60 60 60 60 60 60 0 60 60 
------------------------------------
Test 6:
7 42
1 7 50
0 6 14 18 11 1 0 
1 2 10
60 51 43 74 83 26 2 4 15 40 13 44 67 4 14 24 71 29 15 98 10 27 11 59 86 88 8 3 75 29 47 82 1 65 26 96 13 71 84 1 50 24 67 43 34 42 7 47 24 65 
2 1 10
60 51 43 74 83 26 2 4 15 40 13 44 67 4 14 24 71 29 15 98 10 27 11 59 86 88 8 3 75 29 47 82 1 65 26 96 13 71 84 1 50 24 67 43 34 42 7 47 24 65 
1 3 9
14 16 43 50 2 86 24 8 4 85 58 27 50 57 57 22 77 38 94 67 67 39 0 11 41 34 17 62 39 9 14 66 58 33 57 11 5 63 12 15 86 95 3 83 47 18 66 57 45 36 
3 1 9
14 16 43 50 2 86 24 8 4 85 58 27 50 57 57 22 77 38 94 67 67 39 0 11 41 34 17 62 39 9 14 66 58 33 57 11 5 63 12 15 86 95 3 83 47 18 66 57 45 36 
1 4 8
73 94 68 93 5 24 36 62 74 66 99 25 30 12 7 94 52 51 61 62 15 61 19 20 24 7 88 0 12 86 74 25 48 2 89 47 11 88 47 4 18 78 82 17 11 16 76 22 58 52 
4 1 8
73 94 68 93 5 24 36 62 74 66 99 25 30 12 7 94 52 51 61 62 15 61 19 20 24 7 88 0 12 86 74 25 48 2 89 47 11 88 47 4 18 78 82 17 11 16 76 22 58 52 
1 5 9
3 95 54 8 58 35 46 86 38 17 43 7 22 66 49 18 28 92 33 15 65 40 9 56 78 90 68 63 58 41 57 16 86 45 95 54 62 79 63 43 28 57 18 82 76 27 22 34 21 11 
5 1 9
3 95 54 8 58 35 46 86 38 17 43 7 22 66 49 18 28 92 33 15 65 40 9 56 78 90 68 63 58 41 57 16 86 45 95 54 62 79 63 43 28 57 18 82 76 27 22 34 21 11 
1 6 8
25 62 68 73 36 68 1 22 86 60 40 44 84 81 54 23 87 72 94 39 6 90 64 71 31 44 58 43 81 32 35 16 3 10 3 68 51 16 29 93 45 34 19 27 90 79 13 84 78 24 
6 1 8
25 62 68 73 36 68 1 22 86 60 40 44 84 81 54 23 87 72 94 39 6 90 64 71 31 44 58 43 81 32 35 16 3 10 3 68 51 16 29 93 45 34 19 27 90 79 13 84 78 24 
1 7 10
39 36 14 25 18 78 28 12 65 67 86 32 97 12 15 24 76 42 22 11 51 36 32 71 51 1 91 18 33 35 49 78 11 7 60 77 35 35 79 69 76 62 30 71 45 56 81 86 60 68 
7 1 10
39 36 14 25 18 78 28 12 65 67 86 32 97 12 15 24 76 42 22 11 51 36 32 71 51 1 91 18 33 35 49 78 11 7 60 77 35 35 79 69 76 62 30 71 45 56 81 86 60 68 
2 3 6
34 25 38 49 13 95 44 49 61 31 6 73 7 85 8 58 10 54 3 89 35 95 4 30 21 1 78 8 21 67 97 59 40 2 23 27 90 68 13 5 40 48 77 17 28 73 40 9 64 66 
3 2 6
34 25 38 49 13 95 44 49 61 31 6 73 7 85 8 58 10 54 3 89 35 95 4 30 21 1 78 8 21 67 97 59 40 2 23 27 90 68 13 5 40 48 77 17 28 73 40 9 64 66 
2 4 8
97 44 75 92 75 56 15 58 90 38 26 16 41 18 26 52 53 74 16 64 30 53 63 74 98 64 72 22 83 31 18 25 89 55 1 90 70 50 42 17 15 21 50 22 83 13 0 71 58 61 
4 2 8
97 44 75 92 75 56 15 58 90 38 26 16 41 18 26 52 53 74 16 64 30 53 63 74 98 64 72 22 83 31 18 25 89 55 1 90 70 50 42 17 15 21 50 22 83 13 0 71 58 61 
2 5 2
19 17 99 60 63 29 12 61 84 22 54 18 26 93 54 90 26 43 77 48 14 69 31 34 28 37 18 83 21 20 78 74 62 79 80 33 47 17 48 0 70 38 31 30 34 84 54 95 92 42 
5 2 2
19 17 99 60 63 29 12 61 84 22 54 18 26 93 54 90 26 43 77 48 14 69 31 34 28 37 18 83 21 20 78 74 62 79 80 33 47 17 48 0 70 38 31 30 34 84 54 95 92 42 
2 6 2
4 49 32 8 55 61 25 80 93 27 62 74 36 43 49 98 83 69 65 22 34 39 12 6 74 95 84 94 99 44 36 43 90 58 79 65 75 63 39 96 7 6 52 27 76 75 80 58 18 12 
6 2 2
4 49 32 8 55 61 25 80 93 27 62 74 36 43 49 98 83 69 65 22 34 39 12 6 74 95 84 94 99 44 36 43 90 58 79 65 75 63 39 96 7 6 52 27 76 75 80 58 18 12 
2 7 8
63 90 64 96 79 31 46 58 39 17 3 13 39 95 18 81 94 36 87 41 16 58 63 3 41 1 34 46 65 57 96 26 75 78 33 14 99 39 11 16 83 1 52 82 86 14 44 5 62 65 
7 2 8
63 90 64 96 79 31 46 58 39 17 3 13 39 95 18 81 94 36 87 41 16 58 63 3 41 1 34 46 65 57 96 26 75 78 33 14 99 39 11 16 83 1 52 82 86 14 44 5 62 65 
3 4 1
63 40 37 92 73 47 54 64 41 26 22 82 22 39 91 47 57 69 92 3 15 44 31 41 72 68 50 93 10 15 71 96 8 21 92 77 67 3 6 67 78 52 47 69 42 13 4 19 89 40 
4 3 1
63 40 37 92 73 47 54 64 41 26 22 82 22 39 91 47 57 69 92 3 15 44 31 41 72 68 50 93 10 15 71 96 8 21 92 77 67 3 6 67 78 52 47 69 42 13 4 19 89 40 
3 5 5
26 57 68 23 81 32 68 14 57 55 72 46 60 51 63 33 89 34 91 65 15 94 51 72 96 66 31 76 81 44 19 4 72 89 26 24 48 32 74 27 69 91 31 65 8 34 21 22 91 69 
5 3 5
26 57 68 23 81 32 68 14 57 55 72 46 60 51 63 33 89 34 91 65 15 94 51 72 96 66 31 76 81 44 19 4 72 89 26 24 48 32 74 27 69 91 31 65 8 34 21 22 91 69 
3 6 3
69 41 42 38 44 40 67 3 48 74 24 60 43 21 2 18 16 84 63 72 14 2 66 66 86 64 71 1 83 33 11 34 92 42 98 24 20 17 16 18 43 57 5 73 86 43 34 68 11 93 
6 3 3
69 41 42 38 44 40 67 3 48 74 24 60 43 21 2 18 16 84 63 72 14 2 66 66 86 64 71 1 83 33 11 34 92 42 98 24 20 17 16 18 43 57 5 73 86 43 34 68 11 93 
3 7 4
53 10 65 21 28 48 69 47 63 95 53 45 88 37 79 58 25 63 83 78 37 68 0 31 15 18 97 69 28 55 44 76 7 58 11 95 44 75 75 17 17 98 82 2 77 42 79 36 59 44 
7 3 4
53 10 65 21 28 48 69 47 63 95 53 45 88 37 79 58 25 63 83 78 37 68 0 31 15 18 97 69 28 55 44 76 7 58 11 95 44 75 75 17 17 98 82 2 77 42 79 36 59 44 
4 5 4
14 4 14 89 15 99 82 32 33 77 29 68 41 28 8 27 22 18 73 50 4 25 88 36 58 16 78 31 70 43 43 0 79 33 52 24 44 87 76 85 2 19 44 64 99 8 18 41 30 30 
5 4 4
14 4 14 89 15 99 82 32 33 77 29 68 41 28 8 27 22 18 73 50 4 25 88 36 58 16 78 31 70 43 43 0 79 33 52 24 44 87 76 85 2 19 44 64 99 8 18 41 30 30 
4 6 4
76 4 99 17 22 34 48 47 89 17 97 47 58 25 19 38 18 72 92 59 82 93 87 43 92 43 45 55 22 42 36 20 48 82 5 98 37 97 43 87 71 51 43 51 17 98 32 9 98 26 
6 4 4
76 4 99 17 22 34 48 47 89 17 97 47 58 25 19 38 18 72 92 59 82 93 87 43 92 43 45 55 22 42 36 20 48 82 5 98 37 97 43 87 71 51 43 51 17 98 32 9 98 26 
4 7 9
46 39 70 37 6 77 84 34 92 75 77 70 94 76 75 59 0 64 58 97 66 58 72 4 56 28 41 18 87 7 1 70 11 59 44 54 41 7 54 75 10 46 51 42 92 83 89 29 51 78 
7 4 9
46 39 70 37 6 77 84 34 92 75 77 70 94 76 75 59 0 64 58 97 66 58 72 4 56 28 41 18 87 7 1 70 11 59 44 54 41 7 54 75 10 46 51 42 92 83 89 29 51 78 
5 6 8
34 85 98 96 4 75 83 90 1 75 0 63 28 85 36 69 50 93 36 7 69 99 20 74 39 33 8 99 34 36 42 47 2 79 99 61 70 25 9 77 81 60 47 49 76 56 52 44 63 37 
6 5 8
34 85 98 96 4 75 83 90 1 75 0 63 28 85 36 69 50 93 36 7 69 99 20 74 39 33 8 99 34 36 42 47 2 79 99 61 70 25 9 77 81 60 47 49 76 56 52 44 63 37 
5 7 9
15 17 57 19 49 23 20 1 53 45 97 8 26 77 15 36 25 29 32 75 31 33 11 32 65 85 73 81 15 55 82 22 70 23 87 6 78 35 38 30 67 86 35 17 3 63 95 47 66 11 
7 5 9
15 17 57 19 49 23 20 1 53 45 97 8 26 77 15 36 25 29 32 75 31 33 11 32 65 85 73 81 15 55 82 22 70 23 87 6 78 35 38 30 67 86 35 17 3 63 95 47 66 11 
6 7 4
87 75 11 79 53 90 80 38 80 73 19 69 6 88 91 4 83 56 90 56 74 30 31 9 98 17 88 49 34 84 46 61 93 26 44 1 22 70 34 15 2 54 72 73 42 0 29 27 91 75 
7 6 4
87 75 11 79 53 90 80 38 80 73 19 69 6 88 91 4 83 56 90 56 74 30 31 9 98 17 88 49 34 84 46 61 93 26 44 1 22 70 34 15 2 54 72 73 42 0 29 27 91 75 
=====================================

Iesire:
test 1:
0
0
-----------------------
test 2:
26
3
0 2
0 5
0
----------------------
test 3:
8
6
1 1
2 2
2 3
2 4
2 5
1
----------------------
test 4:
30
15
0 4
0 5
0 6
0 7
0 7
0 6
0 8
0 11
0 10
0 9
0 9
0 10
0 11
0 12
0
--------------------
test5:
5
7
0 1
0 2
0 5
0 4
0 3
0 6
1
------------------------
test 6:
10
2
25 6
15
-----------------------

